Codeforces999 E. Reachability from the Capital

Posted on | In ,

给一个有向图和一个起点，求最少连多少条边，使得从起点出发，可以到达其他所有点

很直观的是，对原图SCC缩点后，与s不在一个强联通分量的点不需要都连边，因为这些点也可能存在边

题解

$scc$ 缩点后，除了 $s$ 所在的强联通块，与其他的新点的入度为 $0$ 的强联通连边是最优的，故缩点后dfs，访问不到新的新点的入度为 $0$ 的强联通数量即为答案